package com.code.leetcode._202507;

//45 跳跃游戏
public class Jump {
    /**
     * 给定一个长度为n的0索引整数数组nums，初始位置为nums[0]
     * 每个元素nums[i]表示从索引i向后跳转的最大长度，换句话说，如果你在nums[i]处，你可以跳转到任意
     * nums[i+j]处 0<=j<=nums[i]  i+j <n
     * 返回到达nums[n-1]的最小跳跃次数，生成的测试用例可以到达nums[n-1]
     * 示例1：输入：nums=[2,3,1,1,4]
     * 输出：2
     * 解释：跳到最后一个位置的最小跳跃数是2，从下标为0跳到下标为1的位置，跳1步，
     * 然后跳3步到达数组的最后一个位置
     * 示例2：nums=[2,3,0,1,4]
     * 输出:2
     **/

    public static void main(String[] args) {
        Jump j = new Jump();
        System.out.println(j.jump(new int[]{2, 3, 1, 1, 4}));
    }

    /**
     * 反向查找到出发的位置
     * 我们的目标是达到数组的最后一个位置，因此我们可以考虑最后异步跳跃前所造的位置，该位置通过跳跃能够
     * 到达最后一个位置。
     * 如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以 贪心
     * 地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置，因此。我们可以从左到右遍历数组，
     * 选择第一个满足要求的位置。
     * 找到最后一步跳跃前的所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在地位置，以此类推，直到找到
     * 数组地开始位置
     **/
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    /**
     * 正向查找可到达地最大位置
     * 如果我们 贪心 地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数
     * 例如，对于数组[2,3,1,2,4,2,3],初始位置是下标0，从下标0开始，最远可以达到下标2，下标0可到达的位置中。
     * 下标1的值是3，从下标1出发可以达到更远的位置，因此第一步到达下标1
     * 从下标1出发，最远可到达下标4，下标1可到达的位置中，下标4的值是4，从下标4出发可以达到更远的位置，因此第二步
     * 到达下标4
     * 在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界，我们从左到右遍历数组，到达边界时，更新边界并
     * 跳跃次数增加1
     * 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，
     * 否则就无法跳到最后一个位置了，如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次 不必要
     * 的跳跃次数 因此我们不必访问最后一个元素
     **/
    public int jump1(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
